package com.sicheng.lc.lc笔试.小红书篇;

import java.util.*;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/9/4 17:36
 */


/**
 * 小明的旅途中需要经过一个国家。这个国家有n个城市，编号为1到n。小明会从1号城市进入，目标是从n号城市出去（即要从1号城市到达n号城市）。有m条双向道路连接这n个城市，每条道路的长度都是1，并且都有一个过路费（是[1,100000]之间的整数）。当小明在一号城市时，他可以预先花费X的费用办一张特权卡，他可以获得所有过路费不超过X的道路的通行权（而其他道路无法通过）。小明一天最多只能走k长度的路，他想知道如果他想在一天之内从1号城市走到n号城市，他最少需要花费多少来办特权卡，即求X的最小值？
 * <p>
 * <p>
 * <p>
 * 输入描述
 * 第一行是3个整数n，m，k，分别表示城市数，道路数和小明一天最多能走的长度。
 * <p>
 * 第二行m个整数，分别为u1, u2, …, um，分别表示第i条道路的一个端点。
 * <p>
 * 第三行m个整数，分别为v1, v2, …, vm，分别表示第i条道路的另一个端点。
 * <p>
 * 第四行m个整数，分别为w1, w2, …, wm，分别表示第i条道路的过路费。
 * <p>
 * 数字间两两有空格隔开。数据保证一定存在解。
 * <p>
 * 输出描述
 * 一行一个整数，表示X的最小值。
 * <p>
 * <p>
 * 样例输入
 * 5 6 3
 * 1 1 2 3 3 4
 * 2 5 3 4 5 5
 * 1 3 1 2 1 1
 * 样例输出
 * 1
 * <p>
 * 提示
 * n<=100000，m<=200000，1<=w<=100000。
 */
public class 最小过路费 {
    public static void main(String[] args) {
        Set<Long> st = new HashSet<>(1 << 15);
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int[] u = new int[m + 1];
        int[] v = new int[m + 1];
        int[] w = new int[m + 1];
        for (int i = 1; i <= m; i++) {
            u[i] = sc.nextInt();
        }
        for (int i = 1; i <= m; i++) {
            v[i] = sc.nextInt();
        }
        for (int i = 1; i <= m; i++) {
            w[i] = sc.nextInt();
        }
        List<int[]>[] g = new List[n + 1];
        Arrays.setAll(g, p -> new ArrayList<>(64));
        for (int i = 1; i <= m; i++) {
            g[u[i]].add(new int[]{v[i], w[i]});
            if (u[i] != 1)
                g[v[i]].add(new int[]{u[i], w[i]});
        }

        //{点,状态,step}  mask的存w,不可以用相同的权访问同一个结点
        PriorityQueue<long[]> q = new PriorityQueue<>(
                100000,
                Comparator.comparingLong(i -> i[1]));
        q.offer(new long[]{1, 0, 0});
        st.add(1L);
        while (!q.isEmpty()) {
            long[] p = q.poll();
            int x = (int) p[0];
            long wx = p[1];
            long s = p[2];
            if (x == n && s <= k) {
                System.out.println(wx);
                return;
            }
            for (int[] d : g[x]) {
                long mask = Math.max(d[1], wx);
                long step = s + 1;
                // 如果已经以相同的状态访问过该结点 就不用再次扩展
                // 如果当前扩展的结点的权 ws >= res, 直接剪枝。x的值不可能比res更小了
                if (!st.contains(mask << 20 | d[0]) && step <= k) {
                    st.add(mask << 20 | d[0]);
                    q.offer(new long[]{d[0], mask, step});
                }
            }
        }
        System.out.println(-1);
    }
}
